package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSymmetric1(root *TreeNode) bool {
	if root == nil {
		return true
	}

	return compare(root.Left, root.Right)
}

func compare(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if p == nil || q == nil {
		return false
	}

	return p.Val == q.Val && compare(p.Left, q.Right) && compare(p.Right, q.Left)
}

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}

	s, l := make([]*TreeNode, 2, 8), 2
	s[0], s[1] = root.Left, root.Right
	for l >= 2 {
		p, q := s[l-1], s[l-2]
		l -= 2
		if p == nil && q == nil {
			continue
		}

		if p == nil || q == nil || p.Val != q.Val {
			return false
		}

		s = append(s[:l], p.Left, q.Right, p.Right, q.Left)
		l += 4
	}

	return true
}
